'''
	func: search():搜索实现；
	变量：
		open:dict,open表;

		close:dict，close表;

		i:int,其顺序即代表进入open表的顺序，该顺序将称为该状态的代号，后续也将使用该值代替；

		j:int,代表当前进入close表的状态，open[j]即可查询到该状态;

		depth:当前的深度

		init_status:dict,初始状态;
			注：(1)键key代表九宫格的某个位置（自上而下，自左向右）;
				(2)值value代表九宫格目前对应的数字，0代表空白值;
				(3)'sat'代表该状态如何由上一个状态变化而来，值包括：'up','down','left','right';
				(4)'father'代表当前状态的父亲状态，用其进入open表的顺序代替
				(5)'depth'代表当前状态的深度

		want_status:dict,目标状态;
'''
class Depth_search():
	def __init__(self,max_depth,init_status):
		self.open={'number':[1]}
		self.close={'number':[]}
		self.init_status=init_status
		self.want_status={1:1,2:2,3:3,4:8,5:0,6:4,7:7,8:6,9:5,0:5,}
		self.i=1
		self.j=1
		self.depth=0
		self.max_depth=max_depth
	def search(self):
		self.open[1]=self.init_status
		self.close[1]=self.init_status
		try:
			while self.open:
				while self.depth>self.max_depth:
					self._pop_open()
					self.j=self.open['number'][-1]
					self.depth=self.open[self.j]['depth']
				if self._check() : break
				self.depth+=1
				self._add_open()
				self.j=self.open['number'][-1]
				
		except Exception:
			return 'Failed... :(\n请提高深度'
		else:
			self._display()
			return self.open[self.j]
	def _pop_open(self): 
		self.open['number'].pop(-1)
		self.close['number'].append(self.j)
		self.close[self.j]=self.open[self.j]
		self.open.pop(self.j)
	def _check(self):
		flag=1
		for num in range (1,9):
			if self.open[self.j][num]!=self.want_status[num]:
				flag=0
		if flag==1:
			print('\nThe result follows:')
			return 1
		return 0

	def _add_open(self):
		self.open['number'].pop(-1)
		self.close['number'].append(self.j)
		self.close[self.j]=self.open[self.j]
		now=self.open.pop(self.j)
		now_zero=now[0]

		#向上移
		if now_zero>3 and now['sta']!='down': 
			now_up={a:b for a,b in now.items()}
			now_up[now_zero]=now_up[now_zero-3]
			now_up[now_zero-3]=0
			now_up[0]=now_zero-3
			now_up['sta']='up'
			now_up['father']=self.j
			now_up['depth']=self.depth
			self.i+=1
			self.open[self.i]=now_up
			self.open['number'].append(self.i)

		#向下移
		if now_zero<7 and now['sta']!='up' :
			now_down={a:b for a,b in now.items()}
			now_down[now_zero]=now_down[now_zero+3]
			now_down[now_zero+3]=0
			now_down[0]=now_zero+3
			now_down['sta']='down'
			now_down['father']=self.j
			now_down['depth']=self.depth
			self.i+=1
			self.open[self.i]=now_down
			self.open['number'].append(self.i)

		#向左移
		if now_zero%3 != 1 and now['sta']!='right':
			now_left={a:b for a,b in now.items()}
			now_left[now_zero]=now_left[now_zero-1]
			now_left[now_zero-1]=0
			now_left[0]=now_zero-1
			now_left['sta']='left'
			now_left['father']=self.j
			now_left['depth']=self.depth
			self.i+=1
			self.open[self.i]=now_left
			self.open['number'].append(self.i)

		#向右移
		if now_zero%3!=0 and now['sta']!='left':
			now_right={a:b for a,b in now.items()}
			now_right[now_zero]=now_right[now_zero+1]
			now_right[now_zero+1]=0
			now_right[0]=now_zero+1
			now_right['sta']='right'
			now_right['father']=self.j
			now_right['depth']=self.depth
			self.i+=1
			self.open[self.i]=now_right
			self.open['number'].append(self.i)


	def _display(self):
		mat=self.open[self.j]
		path=[]
		path.append(mat)
		while True:
			father=self.close[mat['father']]
			path.append(father)
			if father['father'] == 0:  break
			mat=father
		while path !=[]:
			station=path.pop(-1)
			for i in range (9):
				if (i+1)!= station[0]:
					print("{} ".format(station[i+1]),end='')

				else: print("  ",end='')
				if (i+1)%3==0:
					print('')
			print('---------目前深度为{}'.format(station['depth']))
if __name__ == '__main__':
	print("Please input the init status:")
	a1,a2,a3=map(int,input().split())
	a4,a5,a6=map(int,input().split())
	a7,a8,a9=map(int,input().split())
	max_depth=int(input('Please input the Max Depth:'))
	for i in range (9): 
		if [a1,a2,a3,a4,a5,a6,a7,a8,a9][i]==0:
			b=i+1; break;
	init_status={1:a1,2:a2,3:a3,4:a4,5:a5,6:a6,7:a7,8:a8,9:a9,0:b,'sta':'none','father':0,'depth':0}
	print(Depth_search(max_depth,init_status).search())

